// 我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
// （这里，平面上两点之间的距离是欧几里德距离。）
// 你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。

const kClosest = function (points: number[][], K: number): number[][] {
    const resIndex: number = K - 1; // 结果索引
    let left: number = 0;// 左指针
    let right: number = points.length - 1;// 右指针
    let basisIndex: number = -1;// 基础索引
    do {
        basisIndex = kClosest_partition(points, left, right);
        if (basisIndex < resIndex) { // 如果轴点位于左区间就往右找
            left = basisIndex + 1;
        } else if (basisIndex > resIndex) { // 如果轴点位于右区间就往左找
            right = basisIndex - 1;
        }
    } while (basisIndex !== resIndex)
    return points.slice(0, resIndex + 1);
};
// 比较规则
function kClosest_judge(arr1: number[], arr2: number[]): boolean {
    let sum1: number = arr1[0] * arr1[0] + arr1[1] * arr1[1];
    let sum2: number = arr2[0] * arr2[0] + arr2[1] * arr2[1];
    return sum2 < sum1;
}
// 快速选择方法
function kClosest_partition(points: number[][], start: number, end: number): number {
    kClosest_swap(points, start, Math.floor(Math.random() * (end - start + 1) + start)); // 随机交换，防止算法退化
    let pivot: number[] = points[start]; // 轴点元素
    let lastlow: number = start;// 指针指向小于轴点元素区间的最后一个元素
    // 核心算法部分，最好在纸上画一下
    for (let curr = start + 1; curr <= end; curr++) {
        if (kClosest_judge(pivot, points[curr])) {
            kClosest_swap(points, curr, lastlow + 1);
            lastlow++;
        }
    }
    // 交换轴点元素到正确位置
    kClosest_swap(points, lastlow, start);
    return lastlow; // 此时的lastlow指针指向轴点元素索引
}
// 交换方法
function kClosest_swap(arr: number[][], index1: number, index2: number) {
    let temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}


kClosest([
    [1, 3],
    [-2, 2]
], 1)



// 这道题是一道比较典型的TopK问题，唯一的区别在于这里的比较规则
// 不是简单的比大比小，而是一个比较绝对值平方和大小的规则（即原点距离不变）
// 但我们还是可以利用快速选择算法的套路来解决，顺带温习快速排序算法的写法
// 快排的思路是选择一个轴点pivot，将数组分为三部分：
// 1.无序区间
// 2.小于等于 pivot 的元素
// 3.大于 pivot 的元素
// 这里的小于和大于就是基于我们定义的规则来判断
// 之后我们用一个轮次的时间来遍历，在遍历的过程中无序区间是越来越小的
// for循环下的当前元素若比pivot小，那就换到小于等于区间指针的下一个元素，同时小于等于区间指针右移动，当前指针右移动
// 如果当前元素比轴点元素大那就不用管，当前指针右移
// 上面这个On是快速选择算法的核心，建议一定要在纸上画画理解这个过程
// 一轮快速选择算法后，我们返回轴点的索引即可
// 然后在外层的循环中我们需要判断一下当前指针的索引与我们想要的索引是否相等，
// 如果不相等的话我们要重新划定寻找的区间，指到我们找到结果的索引。